The problem of optimally allocating a set of heterogeneous computing resources to the execution of a collection of heterogeneous tasks has been shown to be NP-complete (a problem that becomes exponentially more difficult as the number of variables in the problem increases). Therefore, prior research has focused on developing heuristic approaches to address the problem in specific contexts. In this work, the goal of the heuristic is to minimize the total execution time of a meta-task, where a meta-task is defined to be a collection of independent sub-tasks. Some have proposed using the results of a known successful heuristic as a seed, or starting place, for a search of related solutions in an attempt to more readily find an improvement in overall system performance. System performance is determined by the inverse of the required system execution time to complete all sub-tasks in a given meta-task. Although these prior search techniques may improve on system performance they may require an arbitrarily large execution time to realize any improvement in overall system performance. Additionally, they may require arbitrarily large compute resources to execute properly.
Related approaches include attempts to minimize task lateness in a hard, real-time system by beginning from an arbitrary starting place and performing a depth-first search with no backtracking. However, these approaches do not always find a feasible solution in a reasonable amount of time. A feasible solution refers to one that satisfies all of the system constraints and a reasonable amount of time refers to the amount of time determined to be the system time available for scheduling.
Accordingly, a need remains for a task mapping technique for independent tasks in a heterogeneous computing system that can be executed in reasonable time producing a feasible task mapping and schedule.